from typing import List


class Solution:
    def __init__(self):
        self.count = 0

    def findTargetSumWays(self, nums: List[int], S: int) -> int:

        def dfs(nums: List, i: int, sum: int, S: int):
            if i == len(nums):
                if sum == S:
                    self.count += 1
            else:
                dfs(nums, i+1, sum+nums[i], S)
                dfs(nums, i+1, sum-nums[i], S)

        dfs(nums, 0, 0, S)
        return self.count


class Solution1:
    def __init__(self):
        self.count = 0

    def findTargetSumWays(self, nums: List[int], S: int) -> int:

        def dfs(nums: List, i: int, S: int):
            if i == len(nums):
                if S == 0:
                    self.count += 1
                return
            else:
                dfs(nums, i+1, S-nums[i])
                dfs(nums, i+1, S+nums[i])
        dfs(nums, 0, S)
        return self.count


if __name__ == '__main__':
    x = Solution()
    print(x.findTargetSumWays([1, 1, 1, 1, 1], 3))
